package leetcode.primary;

public class T200 {
    public int numIslands(char[][] grid) {
        int[][] book = new int[grid.length][grid[0].length];
        int count = 0;

        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (book[i][j]==0 && grid[i][j]=='1'){
                    DFS(book,++count,i,j,grid);
                }
            }
        }

        for (int i = 0; i < book.length; i++) {
            for (int j = 0; j < book[0].length; j++) {
                System.out.print(book[i][j]+" ");
            }
            System.out.println();
        }
        return count;

    }

    public void DFS(int[][] book,int count,int i,int j,char[][] grid){
        if (book[i][j]>0){
            return;
        }
        book[i][j]=count;
        if (j>0 && grid[i][j-1]=='1'){
            DFS(book,count,i,j-1,grid);
        }

        if (i>0 && grid[i-1][j]=='1'){
            DFS(book,count,i-1,j,grid);
        }

        if (i<grid.length-1 && grid[i+1][j]=='1'){
            DFS(book,count,i+1,j,grid);
        }

        if (j<grid[0].length-1 && grid[i][j+1]=='1'){
            DFS(book,count,i,j+1,grid);
        }
    }

    public static void main(String[] args) {
        T200 t200 = new T200();
        char[][] chars = new char[][]{{'1','1','1',},
                                        {'0','1','0'},
                                        {'1','1','1',},};
        int numIslands = t200.numIslands(chars);
        System.out.println(numIslands);
    }
}
